package com.wtx.chapter08;

import java.util.Arrays;

/**
 * @description:  Warshall 算法: 获取有向图的传递闭包
 * @author: wtx
 * @createDate: 2020/6/10
 */
public class Warshall {

    // graph: 图的邻接矩阵
    public static int[][] solution(int[][] graph){

        int[][] res = graph;
        for (int k = 0; k < graph.length; k++)
            for (int i = 0; i < graph.length; i++)
                for (int j = 0; j < graph.length; j++)
                    // i->k->j
                    if (res[i][k]==1 && res[k][j]==1)
                        res[i][j] = 1;
        return res;
    }

    public static void main(String[] args) {

        int[][] graph = new int[4][4];
        for (int i = 0; i < graph.length; i++)
            Arrays.fill(graph[i],0-1);

        graph[0][1] = 1;
        graph[1][3] = 1;
        graph[3][0] = 1;
        graph[3][2] = 1;

        int[][] solution = Warshall.solution(graph);
        for (int i = 0; i < graph.length; i++){
            for (int j = 0; j < graph.length; j++)
                System.out.print(solution[i][j]+" ");
            System.out.println();
        }

    }
}
